package com.hot100.mid;

import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;

/**
 * @author zhengTao
 * @version 1.0
 * @description: LRU 缓存
 * @date 2022/9/3 14:24
 */
public class Demo33 {
    class LRUCache {

        LinkedHashMap<Integer, Integer> linkedHashMap=new LinkedHashMap<>();
        //记录每一个key的使用情况，index=0，表示最久没有使用的key
        LinkedList<Integer> list=new LinkedList();
        int cap;
        public LRUCache(int capacity) {
            cap = capacity;

        }

        public int get(int key) {
            Integer value = linkedHashMap.get(key);
            if(value!=null){
                list.remove(Integer.valueOf(key));
                linkedHashMap.remove(key,value);
                linkedHashMap.put(key,value);
                list.add(key);
                return value;
            }
           return -1;

        }

        public void put(int key, int value) {
            linkedHashMap.put(key,value);
            //更新key的使用情况 Integer.valueOf(key) 表示删除key,有则删，没有就算了。 不转成Integer 则表示删除的索引位置的值
            list.remove(Integer.valueOf(key));
            list.add(key);
            int size = linkedHashMap.size();
            //超过原始数组大小，则删除最久没使用到的那个kv值,list.remove(0);最久没使用到的k
            if(size>cap){
                Integer remove = list.remove(0);
                //删除最久没使用到的key
                linkedHashMap.remove(remove);
            }
        }
    }
}
